#include<iostream>
#include<vector>
using namespace std;

int uniquePaths(int m, int n) {
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));
    dp[0][1] = 1;
    for (int i = 1; i <= m; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }
    return dp[m][n];
}
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
    int m = obstacleGrid.size(), n = obstacleGrid[0].size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));
    dp[0][1] = 1;
    for (int i = 1; i <= m; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (obstacleGrid[i - 1][j - 1] == 1) dp[i][j] = 0;
            else dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }
    return dp[m][n];
}

long long findMaximumScore(vector<int>& nums) {
    long long ret = 0, min = nums[0];
    int index = 0;
    for (int i = 1; i < nums.size() - 1; i++)
        if (nums[i] > min) ret += (i - index) * nums[index], index = i, min = nums[i];
    ret += (nums.size() - 1 - index) * nums[index];
    return ret;
}

int main()
{
    vector<vector<int>> vv{ {0,0,0 }, { 0,1,0 }, { 0,0,0 } };
    vector<int> v{ 1,5,4,3 };
    vector<int>::iterator it = v.end();
    uniquePaths(3, 2);
    findMaximumScore(v);
    uniquePathsWithObstacles(vv);
	return 0;
}